The present invention relates to cache memories for electronic computers and, in particular, to a cache system providing for compression of cache data.
The speed at which computers may execute a program is constrained by the time it takes for data and instructions to be transferred from the computer memory to the computer processor. One method of reducing this “memory latency” is through the use of cache memories which are small, high-speed memories with high bandwidth connections to the processor. Data and instructions expected to be needed by the processor are fetched from the main computer memory into the cache memory. When the data is required by the processor, it is readily and quickly available from the cache memory without the need to access the main computer memory.
A larger cache memory increases the likelihood that necessary data is stored in the cache memory and that the time penalty of accessing the main computer memory can be avoided. The costs of larger cache memories, and the need to provide a high bandwidth connection to the processor, however, practically limits the size of the cache memory.
One method of increasing the effective storage capacity of the cache memory, with minimal increases in the area of the cache memory, is by compressing the data in the cache memory. Unfortunately, compressing the cache data slows access to the cache data because the data must be decompressed before it can be used by the processor. This decompression step is typically in the critical time path when data is being requested by the processor.
Whether compression increases the execution speed of a particular program will depend on whether the time savings in reducing cache misses (where needed data is not in the cache) compares favorably with the overhead of cache decompression. Generally, this will depend on the particular program being executed and thus can help or hurt computer performance in different situations.